package binarysearchtree;

/**
 * @Author 比特就业课
 * @Date 2022-11-14
 */
public class BinarySearchTree {
    public static void main(String[] args) {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        int[]arr={1,3,5,6,9,8,7,10};
        for(int i=0;i< arr.length;++i){
            binarySearchTree.insert(arr[i]);
        }
        System.out.println(binarySearchTree.inorder(binarySearchTree.root));
      //  System.out.println(binarySearchTree.search(1));
        //测试删除结点
         binarySearchTree.remove(7);
        System.out.println(binarySearchTree.inorder(binarySearchTree.root));
    }
    // 定义节点类
    private static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }
    // 定义一个根节点的引用
    public TreeNode root;

    /**
     * 查找指定的值是否存在
     * @param value
     * @return
     */
    public boolean search(int value) {
        //判断根结点是否为空
        if(root==null){
            return false;
        }
        //定义遍历节点
        TreeNode cur=root;
        //根据节点值的大小进行遍历
        while (cur!=null){
            if(cur.value==value){
                return true;
            }
            if(cur.value<value){
                cur=cur.right;
            }
            else{
                cur=cur.left;
            }
        }
        return false;
    }

    /**
     * 插入一个元素
     * @param value 要插入的值
     * @return
     */
    public boolean insert(int value) {
       //建立新结点
        TreeNode treeNode = new TreeNode(value);
        //判断根结点是否为空
        if(root==null){
            root=treeNode;
            return true;
        }
        //处理跟结点不为空的情况
        TreeNode cur=root;
        //对树进行遍历
        TreeNode prev=null;
        while(cur!=null){

                if(cur.value==value){
                    return false;
                }
               //将当前结点进行保存
                    prev=cur;
            //对值的大小进行比较
            if(value>cur.value){
                cur=cur.right;
            }
            else{
                cur=cur.left;
            }
        }
        if(prev.value>value){
            prev.left=treeNode;
        }
        else{
            prev.right=treeNode;
        }
        return true;
    }

    /**
     * 删除指定的元素
     * @param value 要删除的元素
     * @return
     */
    public boolean remove(int value) {
        //对根结点进行判断
        if(root==null){
            return false;
        }
        //定义辅助结点进行寻找
        TreeNode parent=null;
        TreeNode cur=root;
        while(cur!=null){
            if(cur.value==value){
                removeNode(parent,cur);
                return true;
            }
            //在cur结点向下遍历前将parent进行移位
            parent=cur;
            if(cur.value<value){
                cur=cur.right;
            }
            else if(cur.value>value){
                cur=cur.left;
            }
        }

        return false;
    }

    /**
     * 分类讨论要删除节点的不同情况
     * @param parent 父节点
     * @param cur 子节点
     */
    private void removeNode(TreeNode parent, TreeNode cur) {
        //处理cur没有左子节点的情况
        if(cur.left==null){
            //如果是根结点
            if(cur==root){
                root=cur.right;
            }
            //如果是父节点的左子节点
            if(parent.left==cur)
            parent.left=cur.right;
            //如果是父节点的右子节点
            if(parent.right==cur)
                parent.right=cur.right;
        }
        //处理cur没有右子结点的情况
        else if (cur.right==null) {
            //处理cur为根的情况
            if(cur==root){
                root=cur.left;
            }
            //处理cur为父节点的左子节点
            if(parent.left==cur){
                parent.left=cur.left;
            }
            //处理cur为父节点的右子节点
            if(parent.right==cur)
            {
                parent.right=cur.left;
            }

        }
        //对cur既有左子节点又有右子结点的情况进行处理
        else{
            //用左子节点的最大值替换或者右子结点的最小值替换
            //notes：此处处理逻辑为替换，之前两种情况处理逻辑为删除，略有不同
            TreeNode curParent=cur;
            //找左子树的右子结点(或者右子树的最左子节点也可以)
            TreeNode target=cur.left;
            while(target.right!=null){
                curParent=target;
                target=target.right;
            }
            //替换
            cur.value=target.value;
            //删除左子节点的最右子结点
            if(curParent.left==target){
                curParent.left=null;
            }
            else {
                curParent.right=null;
            }


        }

    }

    /**
     * 中序遍历
     * @param node
     * @return
     */
    public String inorder(TreeNode node) {
        StringBuilder sb = new StringBuilder();
        if (node == null) {
            return sb.toString();
        }
        // 先处理左
        String left = inorder(node.left);
        sb.append(left);
        // 处理根节点
        sb.append(node.value + " ");
        // 处理右
        String right = inorder(node.right);
        sb.append(right);
        return sb.toString();
    }
}
